/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年11月20日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int size = s.size();
        vector<vector<bool>> dp(size, vector<bool>(size, false));
        int result = size;
        for(int i = 0; i < size; i++){
            dp[i][i] = true;
        }

        for(int i = 1; i < size; i++){
            for(int j = 0; j < i; j++){
                if(s[i] == s[j] &&((i-j) == 1 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    result++;
                }
            }
        }

        return result;
    }
};
